#coding=utf-8

#二分搜索
A = [0,1,1,2,3,3,3,3,4,5,5,7,7,7]
def L(A:list,x:int)->int:
    left = 0
    right = len(A)-1
    while left<right:
        mid =  (left+right) // 2
        if A[mid] >= x:
            right = mid
        else:
            left = mid + 1
    return right

#子集和问题
def sort_combinate(L:list,n:int) -> list:
    '''
    从L中选出n个不重复的元素序列
    根据递归的时间复杂度公式计算，递归用的时间复杂度是O(n^2)而判断是否子集和的时间复杂度为O(n^2),则最终的时间复杂度为0(n^2)
    :param L:
    :param n:
    :return: list
    '''
    res = []
    if n == 1:
        for i in L:
            res.append([i])
        return res
    elif n == len(L):
        return [L]
    else:
        for each_list in sort_combinate(L[1:],n-1):
            res.append([L[0]] + each_list)
        for each_list in sort_combinate(L[1:],n):
            res.append(each_list)
        return res

alist = [5,-2,4,2]
answer = []
for i in range(len(alist)):
    for j in sort_combinate(alist,i+1):
        if sum(j) == 0:
            answer.append(j)
print(answer)

